package top.humbleyuan.dp;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 21:56
 * @Des 打家劫舍
 */
public class LeetCode_198 {
    public static void main(String[] args) {
        int[] nums = {1,2,3,1};
        if(nums == null || nums.length == 0) {
            System.out.println(0);
        }

        /**
         * dp[i]:偷取到第i家的最大值
         * dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
         *
         * 节省空间可以只用两个变量存储
         */
        int preMax = 0;
        int curMax = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int temp = curMax;
            curMax = Math.max(preMax + nums[i], curMax);
            preMax = temp;
        }

        System.out.println(curMax);
    }
}
